package com.wish.algorithm;

/**
 * Created by suliucheng on 2021/4/18 15:48
 * Directions: 把8个皇后放在棋盘上使其互不攻击，请问一共有多少种排法？并且打印
 */
public class QueuesOfDeath {
    /**
     * 皇后的个数
     */
    private int max = 8;
    /**
     * 索引值+1 是棋盘的横坐标 ，array[i] 是棋盘的纵坐标
     */
    private int[] array = new int[max];

    public int count = 0;
    /**
     *
     * @param n 为棋盘横坐标
     */
    public void put(int n){
        if(n == max){
            count++;
            show();
            return;
        }
        for (int i = 0; i < max; i++) {
            //先把皇后放上去，然后判断是否冲突，冲突就继续放置
            array[n]=i;
            if(notConflict(n)){
                put(n+1);
            }
        }
    }

    /**
     * 当不同的皇后在同一列或者在对角线上的时候 产生冲突
     * @param n
     * @return
     */
    private boolean notConflict(int n) {
        //和前面几个比较冲突不冲突
        for (int i = 0; i < n; i++) {
            if(array[i]==array[n] || Math.abs(n-i)==Math.abs(array[n]-array[i])){
                return false;
            }
        }
        return true;
    }

    /**
     * 展示放好的棋盘
     */
    public void show() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}
